#pragma once

#include <string>
#include <vector>

namespace solution_022
{

class Solution
{
public:
    std::vector<std::string> generateParenthesis(int n)
    {
        std::string p;
        p.reserve(n * 2);
        p.push_back('(');
        backtrack(p, 1, n);
        return m_comb;
    }

private:
    void backtrack(std::string& p, int left_open, int n)
    {
        if (left_open == n) {
            m_comb.push_back(p);
            m_comb.back().resize(n * 2, ')');
            return;
        }

        p.push_back('(');
        backtrack(p, left_open + 1, n);
        p.pop_back();

        if (left_open * 2 > (int)p.size()) {
            p.push_back(')');
            backtrack(p, left_open, n);
            p.pop_back();
        }
    }

    std::vector<std::string> m_comb;
};

}  /* namespace solution_022 */
